Collinearity

One way of eliminating unnecessary waypoints in your path is to evaluate whether or not those points are collinear, and remove everything but the endpoints of each collinear series of points. For three points p_1, p_2 and p_3 to be collinear, the determinant of the matrix that includes the coordinates of these three points as rows must be equal to zero:

For points in three dimensions this is a necessary but not sufficient condition for collinearity. However, for two dimensional points, evaluating the same determinant with the z coordinate simply set to 1, the determinant being equal to zero indicates that the area of the triangle described by those three points is zero and is a sufficient condition for collinearity:

And the determinant simplifies to :

With Python you can easily evaluate a determinant using numpy:

# Import numpy
import numpy as np

# Define some 2D points
p1 = np.array([1, 2])
p2 = np.array([2, 3])
p3 = np.array([3, 4])

# Define a simple function to add a z coordinate of 1
def point(p):
    return np.array([p[0], p[1], 1.])

# Add points as rows in a matrix
mat = np.vstack((point(p1), point(p2), point(p3)))
# Compute and print the determinant of the matrix
det = np.linalg.det(mat)
print(det)
>>> 0.0

So that works, but in the real world your points might not be exactly on a line, but for all intents and purposes you can treat them as collinear. For example, consider the case where:

# Define some 2D points
p1 = np.array([1.001, 2.002])
p2 = np.array([1.999, 3.001])
p3 = np.array([2.99, 4.002])

# Add points as rows in a matrix
mat = np.vstack((point(p1), point(p2), point(p3)))
# Compute and print the determinant of the matrix
det = np.linalg.det(mat)
print(det)
>>> 0.008989

If these values are in metres, then most likely you can accept these points as collinear for planning a path for your flying car. So a necessary addition if you're using this method is to introduce a threshold, let's call it epsilon, which indicates how close to zero the determinant must be in order to consider the points to be collinear. This allows you to impose a criterion for accepting points that are almost collinear. So you could add the following to your implementation:

collinear = False
epsilon = 1e-2
# Compare the absolute value of the determinant with epsilon
if np.abs(det) < epsilon:
    collinear = True

So that all works just fine, but np.linalg.det() uses floating point math, which is necessary if your points are non-integer. If, however, you're running on a low-power flight computer and working with grid cell locations, which have integer values, you'd rather be using integer arithmetic.

Collinearity Exercise

In this exercise, you'll write a function to evaluate the determinant for three points using the np.linalg.det() function including a threshold epsilon for collinearity. You'll write another function to compute the determinant in the 2D case using only integer arithmetic and compare with the speed of the 3D implementation. Your takeaways here will be two choices for collinearity testing, one which optimizes for speed, and the other which allows you to set a collinearity threshold for ever-so-slightly wandering lines.

Good luck! And for a peek at our solution scroll to the link at the bottom of the notebook.